﻿using System;
using System.Collections.Generic;


/*
 * 2021-03-06  JackLee
 * https://leetcode-cn.com/problems/next-greater-element-i/
 * 
 * 解题思路：
 *  遍历nums1中的元素，在nums2中找到对应的元素后，再继续向后执行找到第一个大于该元素的元素，然后返回该元素，不存在则返回-1
 * 
 * */
namespace NextGreaterElement
{
    public class Class1
    {
        public int[] NextGreaterElement(int[] nums1, int[] nums2)
        {
            int[] result = new int[nums1.Length];
            for (int i = 0; i < nums1.Length; i++)
            {
                for (int j = 0; j < nums2.Length; j++)
                {
                    if(nums2[j]==nums1[i])
                    {
                        while (j<nums2.Length&& nums2[j] <= nums1[i])
                        {
                            j++;
                        }
                        result[i] = j < nums2.Length ? nums2[j] : -1;
                        break;
                    }
                }
            }
            return result;
        }

        /*
         * nums1是nums2的子级，因此我们可以先遍历nums2，求得nums2中每个元素的更大元素并存储
         * 然后在遍历nums1中的元素，并从存储中取值即可
         * */
        public int[] NextGreaterElement2(int[] nums1,int[] nums2)
        {
            Stack<int> stack = new Stack<int>();
            Dictionary<int, int> dics = new Dictionary<int, int>();

            stack.Push(nums2[0]);
            for (int i = 1; i < nums2.Length; i++)
            {
                //注意这里的判断条件是大于每次取值时的栈顶元素
                //int tmp = stack.Peek();
                //if (nums2[i]>tmp)
                //{
                //    while (stack.Count>0)
                //    {
                //        dics.Add(stack.Pop(), nums2[i]);
                //    }
                //}
                while (stack.Count>0&&nums1[i]>stack.Peek())
                {
                    dics.Add(stack.Pop(), nums1[i]);
                }
                stack.Push(nums2[i]);
            }

            //遍历完成后，注意要清空stack
            while (stack.Count>0)
            {
                dics.Add(stack.Pop(), -1);
            }
            //经过以上步骤，nums2中所有元素的更大元素已存储在dics中

            for (int i = 0; i < nums1.Length; i++)
            {
                nums1[i] = dics[nums1[i]];
            }

            return nums1;
        }
    }
}
